# 【题目】 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，
# 如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛?
# 【举例】 这个矩阵中有三个岛
# [[001010]
#  [111010]
#  [100100]
#  [000000]]


def num_island(matrix):
    m, n = len(matrix), len(matrix[0])
    res = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                res += 1
                infect(matrix, m, n, i, j)

    return res


def infect(matrix, m, n, i, j):
    if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] != 1:
        return
    matrix[i][j] = 2
    infect(matrix, m, n, i+1, j)
    infect(matrix, m, n, i, j+1)
    infect(matrix, m, n, i, j)
    infect(matrix, m, n, i, j-1)


if __name__ == "__main__":
    lst = [[0, 0, 1, 0, 1, 0],
           [1, 1, 1, 0, 1, 0],
           [1, 0, 0, 1, 0, 0],
           [0, 0, 0, 0, 0, 1]]
    print(num_island(lst))
